import { ICompareFunction, Compare, defaultCompare, reverseCompare } from '../util';

/**
 * 堆(heap)也就叫二叉堆，是一种完全二叉树。树的每一层（除了最后一层）都有左右
 * 子节点，最后一层的叶节点尽可能都是左节点；它要么是最小堆要么是最大堆，最小堆
 * 的意思是父节点小于等于左右子节点，最大堆的意思是父节点大于等于左右子节点。
 * 二叉堆可以快速找出最大值和最小值，所以常被用于优先队列，也用于堆排序算法。
 * 二叉堆同层的大小是不明确的，取决于插入的先后顺
 */
export class MinHeap<T> {
    protected heap: T[] = []; // 用数组来存储
    protected compareFn: ICompareFunction<T>; // 比较函数
    constructor(compareFn: ICompareFunction<T> = defaultCompare) {
        this.compareFn = compareFn;
    }
    /**
     * 左子节点的index
     */
    private getLeftIndex(index: number): number {
        if (index < 0) {
            return undefined;
        }
        return index * 2 + 1; // 每一层都是2的倍数，也就是父节点和子节点是两倍的关系
    }
    /**
     * 右子节点的index
     */
    private getRightIndex(index: number): number {
        if (index < 0) {
            return undefined;
        }
        return index * 2 + 2; // 每一层都是2的倍数，也就是父节点和子节点是两倍的关系
    }
    /**
     * 父节点的index
     */
    private getParentIndex(index: number): number {
        if (index <= 0) {
            return undefined;
        }
        return Math.floor((index - 1) / 2); // 每一层都是2的倍数，也就是父节点和子节点是两倍的关系
    }
    /**
     * 向二叉堆插入一个新值
     */
    public insert(value: T): boolean {
        if (value != null) {
            this.heap.push(value); // 放在数组末尾
            this.siftUp(this.heap.length - 1); // 从二叉堆的新元素处自下而上的检查
            return true;
        }
        return false;
    }
    /**
     * 上移操作，让新插入的值在合适的位置（跟父节点比大小）
     */
    private siftUp(index: number) {
        let parentIndex = this.getParentIndex(index);
        // index为0代表插入的是根节点就无需“上移操作”了；父节点大于新插入节点，就交换两个元素的位置
        while (index > 0 && this.compareFn(this.heap[parentIndex], this.heap[index]) === Compare.BIGGER_THAN) {
            this.swap(this.heap, index, parentIndex);
            index = parentIndex;
            parentIndex = this.getParentIndex(index);
        }
    }
    /**
     * 交换数组中两个元素的位置
     */
    private swap(array: T[], a: number, b: number) {
        const tmp: T = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }
    /**
     * 移除最大堆的最大值或最小堆的最小值
     */
    public extract(): T {
        if (this.isEmpty()) {
            return undefined;
        }
        if (this.size() === 1) {
            return this.heap.shift();
        }
        const result = this.heap[0]; // 二叉堆的最顶端
        this.heap[0] = this.heap.pop(); // 将数组的最后一项补到二叉堆的最顶端
        this.siftDown(0); // 然后从二叉堆的开头进行下移操作，目的是重新梳理二叉堆
        return result;
    }
    /**
     * 下移操作
     */
    private siftDown(index: number, heapSize?: number) {
        let element = index;
        const size = heapSize == null ? this.size() : heapSize;
        const leftIndex = this.getLeftIndex(index);
        const rightIndex = this.getRightIndex(index);
        // 左子节点存在，左子节点比当前节点小
        if (leftIndex < size && this.compareFn(this.heap[element], this.heap[leftIndex]) === Compare.BIGGER_THAN) {
            element = leftIndex; // 取最小
        }
        // 右子节点存在，右子节点比当前节点和左子节点还小
        if (rightIndex < size && this.compareFn(this.heap[element], this.heap[rightIndex]) === Compare.BIGGER_THAN) {
            element = rightIndex; // 取最小
        }
        if (element !== index) {
            this.swap(this.heap, element, index); // 交换
            this.siftDown(element, size);
        }
    }
    /**
     * 将新数组传入，进行处理后变为二叉堆形式的数组
     */
    public arrayToHeap(array: T[]): T[] {
        if (array != null) {
            this.heap = array;
        }
        const MaxIndex: number = this.getParentIndex(this.heap.length - 1); // 最后一项的父节点
        for (let i = MaxIndex; i >= 0; i --) { // 从最后一项的父节点开始自下而上的进行下移
            this.siftDown(i);
        }
        return this.heap;
    }
    /**
     * 返回经过堆排序的数组
     * this.compareFn为defaultCompare是最小堆，但输出是降序的
     * this.compareFn为reverseCompare是最大堆，但输出是升序的
     */
    public heapSort(): T[] {
        let heapSize = this.heap.length;
        while (heapSize > 1) {
            this.swap(this.heap, 0, -- heapSize);
            this.siftDown(0, heapSize);
        }
        return this.heap;
    }
    /**
     * 二叉堆的大小
     */
    public size(): number {
        return this.heap.length;
    }
    /**
     * 二叉堆是否为空
     */
    public isEmpty(): boolean {
        return this.size() <= 0;
    }
    /**
     * 最小堆就返回最小值，最大堆就返回最大值
     */
    public findMinimum(): T {
        return this.isEmpty() ? undefined : this.heap[0];
    }
    /**
     * 返回二叉堆的数组形式
     */
    public getAsArray(): T[] {
        return this.heap;
    }

    /**
     * 清空二叉堆
     */
    public clear() {
        this.heap = [];
    }
}
/**
 * 最大堆
 */
export class MaxHeap<T> extends MinHeap<T> {
    constructor(compareFn: ICompareFunction<T> = defaultCompare) {
        super(compareFn);
        this.compareFn = reverseCompare(compareFn);
    }
}
